//可以利用url哈希成uint32,存储成map[uint32]string，但使用空间，判断速度都比布隆过滤器慢
//UInt32 - [0 : 4,294,967,295]
//假设我们目前需要对1 千万的网页地址判重，利用位图,数字范围最好在 1 到 1 亿之间，只需要 1 亿个二进制位，最多也就是 12MB 左右的存储空间就够了
//更加具体按照公式的计算，设位图大小为m，样本数量为n=1千万，URL最长不超过64B，所容忍的误判率p为p=0.0001
//计算m = 20n = 24MB，对应最大值应该为201,326,592
//k = 14，即需要14个哈希函数
//通过 m = 20n， k = 14，可以通过以下公式算出设计的布隆过滤器的真实误判率为0.00006。
package bloomFilter

import (
	"hash/crc32"
)

//定义一个全局布隆过滤器
var BloomFilter = newBitMap()

const (
	k uint32 = 14
	m uint32 = 201326592
)

// 位图
type BitMap struct {
	Bytes []byte // 从0到Max，每8个数对应一个byte存储，如果该位存了数字则设置为1
	Max   uint32 //可存储的最大值，这里设置为 201326592
}

func newBitMap() *BitMap {
	bytes := make([]byte, m/8+1) // Go中byte类型占8bit，也即是1个字节
	return &BitMap{Max: m, Bytes: bytes}
}

// 存储数字num
func (b *BitMap) set(num uint32) {
	byteIndex := num / 8
	bitIndex := num % 8
	b.Bytes[byteIndex] |= (1 << bitIndex)
}

// 判断是否存在数字k，返回true代表存在
func (b *BitMap) get(num uint32) bool {
	byteIndex := num / 8
	bitIndex := num % 8
	return (b.Bytes[byteIndex] & (1 << bitIndex)) != 0
}

//先将将url网址,哈希算出来uint32
func (b *BitMap) hashURL(url string) uint32 {
	if len(url) < 64 {
		//声明一个数组长度为64
		var srcatch [64]byte
		//拷贝数据到数组中，保证长度最少64
		copy(srcatch[:], url)
		//使用IEEE 多项式返回数据的CRC-32校验和
		return crc32.ChecksumIEEE(srcatch[:len(url)])
	}
	return crc32.ChecksumIEEE([]byte(url))
}

//再使用 k 个哈希函数，对同一个数字进行求哈希值，得到 k 个不同的哈希值，都设置成 1 ，用 k 个二进制位，来表示一个数字的存在
func (b *BitMap) Store(url string) {
	firstHash := b.hashURL(url)
	var i uint32
	for i = 0; i < k; i++ {
		temp := ((firstHash << i) | (firstHash >> i)) % b.Max //自己随便写的方法
		b.set(temp)
	}
}

//看这 k 个哈希值，如果都是 1，则说明，这个数字存在，如果有其中任意一个不为 1，那就说明这个数字不存在
func (b *BitMap) Find(url string) bool {
	firstHash := b.hashURL(url)
	var i uint32
	for i = 0; i < k; i++ {
		temp := ((firstHash << i) | (firstHash >> i)) % b.Max //自己随便写的方法
		ok := b.get(temp)
		if ok == false {
			return false
		}
	}
	return true
}
